Content addressable memory (CAM), including ternary content addressable memory (TCAM), can be used in network forwarding elements (e.g., network elements) to perform high data rate search operations. CAMs and TCAMs are hardware search engines including memory that hold rules to be searched. CAMs have two states whereby the value in a bit in a rule has to be 0 or 1. TCAMs have three states: 0, 1 and X (or Don't Care).
The speed offered by a TCAM solution may be essential for some implementations. For example, network elements can use TCAMs to implement policy based routing, in which polices are defined that apply to some units of network data but do not apply to other units of network data. TCAMs can be used to implement access control lists within the network elements that are applied to units of network data upon entry (ingress) and/or exit (egress) from the network element. Additionally, a sufficiently large TCAM can be used to make forwarding decisions for network data by defining at least a portion of the forwarding data (e.g., routing table) as a set of TCAM rules.
However, for a given set of rules that define a policy or forwarding database, a TCAM-based solution compared to a memory-based solution is both more expensive and higher in power consumption. These drawbacks can limit the memory size of a TCAM solution, which can limit the number of rules that may be defined.